Matemática Discreta: Os Fundamentos da Contagem

Contar é a arte de determinar o tamanho de conjuntos finitos sem o trabalho tedioso da enumeração física. Aproveitando estruturas lógicas, podemos resolver problemas que vão de combinações simples de cardápios até permutações criptográficas complexas.

A Lógica do "OU" e do "E"

Dois pilares sustentam todo o campo da combinatória. Sua aplicação depende inteiramente de vermos uma tarefa como uma escolha única entre várias categorias ou como uma sequência de escolhas.

O Princípio da Adição (Regra da Soma)

Se um conjunto $X$ for particionado em subconjuntos disjuntos $X_1, X_2, \dots, X_n$, então o número total de elementos $|X|$ é a soma dos tamanhos desses subconjuntos:

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

Analogia: Escolher uma refeição no Kay’s Quick Lunch escolhendo ou um sanduíche do cardápio de Pratos Principais OU um petisco do cardápio de Entradas. Você não pode ter os dois; escolhe apenas um item.

O Princípio da Multiplicação (Regra do Produto)

Se uma atividade consiste em $t$ passos sucessivos, onde o passo $i$ tem $n_i$ resultados possíveis, o número total de maneiras de concluir a tarefa é o produto das possibilidades em cada passo:

$$N = n_1 \times n_2 \times \dots \times n_t$$

Analogia: Configurar um caminhão "Big Pickup". Você deve escolher um motor (5 opções) E um estilo de cabine (3 opções). O número total de configurações é igual a $5 \times 3 = 15$.

Implementação em Código e Complexidade

Na ciência da computação, esses princípios se manifestam em estruturas de laço. Laços sequenciais representam o Princípio da Adição, enquanto laços aninhados representam o Princípio da Multiplicação.

// Princípio da Adição (execuções: m + n)

para i = 1 até m: imprimir(i)

para j = 1 até n: imprimir(j)

// Princípio da Multiplicação (execuções: m * n)

para i = 1 até m:

para j = 1 até n:

imprimir(i, j)

🎯 Princípio Central

Diferencie por palavras-chave: "OU" indica Adição (escolhas mutuamente exclusivas), enquanto "E" ou "Sucessivo" indica Multiplicação (passos independentes em uma sequência).

QUESTÃO 1

Quantas refeições no Kay’s Quick Lunch (Figura 6.1.1) consistem em um petisco e uma bebida, assumindo que há 3 petiscos e 4 bebidas?

QUESTÃO 2

No trecho de código fornecido, quantas vezes os comandos de impressão são executados no total? [Código: para i = 1 até m, imprimir(i), para j = 1 até n, imprimir(j)]

m × n

$m + n$

$m^n$

$n^m$

QUESTÃO 3

Quantas strings de comprimento 3 podem ser formadas usando as letras {A, B, C, D, E} se permitirmos repetições?

125

243

QUESTÃO 4

Usando a chave pública (n=713, e=29), qual é a criptografia da mensagem M = 333?

333

557

128

712

QUESTÃO 5

Quantas strings de comprimento 3 usando as letras {A, B, C, D, E} contêm a letra A pelo menos uma vez (repetições permitidas)?

125

Desafio: Raciocínio Combinatório Avançado

Caminhões, Triângulos e Gaiolas de Pombos

Cenário: Os caminhões grandes atraem por causa das maneiras aparentemente infinitas de personalização. Um artigo do New York Times sugere que você precisa das habilidades matemáticas de Will Hunting para calcular as configurações. Vamos analisar um modelo com 5 opções de motores (3.9L V6, 5.2L V8, 5.9L V8, 5.9L Diesel Turbo, 8L V10).

Defina ordem lexicográfica e explique por que é útil em estruturas de contagem.

Solução: A ordem lexicográfica é uma generalização da ordem alfabética das palavras em um dicionário para sequências de símbolos ordenados. Dadas duas sequências $a_1...a_n$ e $b_1...b_n$, dizemos que $a < b$ se no primeiro índice $i$ onde $a_i \neq b_i$, temos $a_i < b_i$. É útil porque fornece uma maneira sistemática de listar todas as permutações ou combinações sem omissão ou repetição.

O que é uma permutação de $x_1, \dots, x_n$? Forneça uma definição formal.

Solução: Uma permutação de um conjunto de objetos distintos é uma disposição ordenada desses objetos. Para um conjunto de $n$ elementos, uma permutação é uma bijeção do conjunto $\{1, 2, \dots, n\}$ para si mesmo, onde a ordem dos elementos na sequência resultante importa.

Demonstre que, se cinco cartas forem escolhidas de um baralho comum de 52 cartas, pelo menos duas cartas são do mesmo naipe.

Solução: Isso é uma aplicação do Princípio da Casa dos Pombos. Há 4 naipes possíveis (as "gaiolas") e 5 cartas são escolhidas (os "pombos"). Como $5 > 4$, pelo Princípio da Casa dos Pombos, pelo menos um naipe deve conter $\lceil 5/4 \rceil = 2$ cartas. Assim, pelo menos duas cartas devem compartilhar um naipe.

De quantas formas podemos selecionar oito bolas de uma bolsa contendo bolas vermelhas, azuis e amarelas (pelo menos 8 de cada)? (Dificuldade: Palavras-Chave: 18, Comprimento: Curto)

Solução: Este é um problema de combinações com repetição. Usando a fórmula das estrelas e barras $C(n+r-1, r)$ onde $n=3$ categorias e $r=8$ seleções: $C(3+8-1, 8) = C(10, 8) = C(10, 2) = (10 \times 9) / 2 = 45$ formas.